package 字符串算法;

public class 实现strStr {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.strStr("hello", "ll");
        System.out.println(i);

    }


}
class Solution{
    public void getnext(int[] next , String s){
        int j = -1;
        next[0] = j;
        for (int i = 1 ; i<s.length();i++){
            while (j>=0 && s.charAt(i) != s.charAt(j+1)){
                j = next[j];  //向前回溯
            }
            if (s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }

    public int strStr(String haystack,String needle) {
       if (needle.length()==0){
           return 0;
       }
       int[] next = new int[needle.length()];
       getnext(next,needle);
       int j = -1;
       for (int i = 0 ;i<haystack.length();i++){
           while (j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
               j = next[j];
           }
           if (haystack.charAt(i)==needle.charAt(j+1)){
               j++;
           }
           if (j==needle.length()-1){
               return (i-needle.length()+1);
           }
       }

       return -1;

    }

}